Memory management relates to managing memory resources in a computer system. This management may include allocating memory used by programs running on the computer system as well as reclaiming memory that had been allocated to the programs but is no longer used by the programs. In many programming languages, memory allocated to a program is often allocated from a heap. A heap, as used herein, relates to an area of memory that may be used for dynamic memory allocation.
In some languages, management of the heap is the programmer's responsibility. This approach to memory management is often termed manual memory management. The complexity of manual memory management may lead to many common errors that may cause unexpected or erroneous program behavior and crashes. As a result, a large portion of developer time may be spent debugging and trying to correct such errors.
One common error that may occur when using manual memory management is space leaks. Space leaks occur when allocated memory is no longer referenced but is not released. For example, if a program frees space utilized by a linked list but just frees the first element of the list, the remaining list elements may no longer be reachable by the program and consequently may neither be used nor recovered. If enough leaks occur, they may keep consuming memory until all available memory is exhausted.
An alternative approach to manual memory management is automatic memory management. Automatic memory management relates to a technique for managing memory that often includes provisions for automatically reclaiming memory that is “unreachable” by software (e.g., programs) running on a system. Automatic memory management may be implemented as a service that is part of a programming language or an extension to the language.
Garbage collection is a form of automatic memory management that relates to automatically finding and reclaiming unreachable memory. Garbage collection is widely utilized by many modern object-oriented programming languages. Garbage collection prevents memory loss due to, for example, space leaks, because objects that are unreachable are automatically reclaimed.
Garbage collection is often implemented in the form of a garbage collector. A garbage collector is responsible for, inter alia, reclaiming areas of memory that are considered to be unreachable. These areas are often said to be “dead” or “garbage” and are considered eligible for reclaiming by the garbage collector. Areas in memory that are reachable are often said to be “live”. These areas may include areas that have been allocated to and are actively used by the software. Live areas are not collected by the garbage collector.
Various techniques may be used by garbage collectors to collect garbage. One well-known technique is the “mark-compact” technique. This technique typically involves marking all live areas of memory then reclaiming areas of memory that are not marked which are assumed to be garbage. The process of reclaiming may involve “sliding” live areas over the dead areas to compact all of the live areas at one end of the memory. References to the live areas that were slid are then updated to reflect their new location. The end result is usually a memory that has all the live areas at one end of the memory followed by a single contiguous area of unused memory.
Sliding large areas of memory and updating references to them, however, may be very expensive in terms of time and utilization of computational resources. Since memory tends to be quite plentiful these days, “wasting” some amount of memory in order to improve efficiency and cut down on excessive sliding is generally acceptable and an attractive approach. Thus, some sliding garbage collection implementations may allow a certain amount of memory to be “wasted” in order to cut down on the number of times live areas of memory need to be slid.
For example, assume a memory contains a 1 megabyte (MB) live area followed by an eight-byte dead area, a 10 MB live area and a 10 MB dead area, in that order. A garbage collector may be configured to waste the eight-byte dead area in order to avoid having to slide the 10 MB live area over the eight-byte dead area to reclaim it.
Some garbage collection techniques employ a “dense prefix” that may be used to identify areas of memory that should and should not be moved. Typically, anything before the dense prefix is not moved and live areas after the dense prefix are moved. Thus, in the example above, establishing the dense prefix right after the 1 MB live area causes the 10 MB live area to be moved over the eight-byte dead area. On the other hand, establishing the dense prefix right after the 10 MB live area would cause the 10 MB to remain and not be moved.